#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.

"""
https://blog.csdn.net/yangtzhou/article/details/83450810
"""

import math


class Solution:
    def __init__(self, points):
        self.points = sorted(points)        # [x, y]
        self.len = len(points)
        self.dis_memory = {}
        # self.path_memory = {}
        self.dis_memory[(0, 0)] = 0
        self.dis_memory[(0, 1)] = self.dis_of_two_point(0, 1)
        self.bitonic_rec(self.len-1, self.len-1)

        self.min_dis = self.dis_memory[ (self.len-1, self.len-1) ]

    def bitonic_rec(self, left_idx, right_idx):
        # 从 left_idx 到最左边, 从最左边回到right_idx
        assert left_idx <= right_idx

        key = left_idx, right_idx
        if key in self.dis_memory:
            return self.dis_memory[key]

        # if left_idx == 0:

        if left_idx == right_idx or left_idx == right_idx - 1:
            min_dis = 2**31
            # for mid_idx in range(0, right_idx):
            for mid_idx in range(0, left_idx):
                try_dis = self.bitonic_rec(mid_idx, left_idx) + self.dis_of_two_point(mid_idx, right_idx)
                if try_dis < min_dis:
                    min_dis = try_dis
                    # TODO: 记录path(mid)

        # elif left_idx == right_idx-1:
        #     min_dis = 2**31
        #     for mid_idx in range(0, right_idx):
        #         try_dis = self.bitonic_rec(mid_idx, left_idx) + self.dis_of_two_point(mid_idx, right_idx)
        #         if try_dis < min_dis:
        #             min_dis = try_dis

        else:
            assert left_idx < right_idx - 1
            min_dis = self.bitonic_rec(left_idx, right_idx-1) + self.dis_of_two_point(right_idx-1, right_idx)

        self.dis_memory[key] = min_dis
        print(key, min_dis)
        return min_dis

    def dis_of_two_point(self, a, b):
        ax, ay = self.points[a]
        bx, by = self.points[b]
        return math.sqrt(abs(ax-bx)**2 + abs(ay-by) ** 2)

def test():
    # 算法导论的示例数据: 答案是25.58
    points = [(0, 6), (1, 0), (2, 3), (5, 4), (6, 1), (7, 5), (8, 2)]
    s = Solution(points)
    print(s.min_dis)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
